﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"
#include <chrono>
using namespace std::chrono;
using namespace Microsoft::VisualStudio::CppUnitTestFramework;



namespace Other
{
	TEST_CLASS(LC2343)
	{
		//LC2343. 裁剪数字后查询第 K 小的数字
		class Solution {
		public:
			vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
				const int N = nums.size();
				const int M = nums.front().size();
				vector<vector<int>> queIndexs(M + 1);
				for (int i = 0; i < queries.size();i++) {
					queIndexs[queries[i][1]].emplace_back(i);
				}
				vector<int> indexs(N),ret(queries.size());
				iota(indexs.begin(), indexs.end(), 0);
				for (int i = 0; i < M; i++) {
					const int cur = M - 1 - i;
					stable_sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return nums[i1][cur] < nums[i2][cur]; });
					for (const auto& inx : queIndexs[i + 1]) {
						ret[inx] = indexs[queries[inx][0] - 1];
					}
				}
				return ret;
			}
		};
	public:
		vector<string> nums;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			nums = { "102","473","251","814" }, queries = { {1,1},{2,3},{4,2},{1,2} };
			auto res = Solution().smallestTrimmedNumbers(nums, queries);
			AssertEx({2, 2, 1, 0}, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { "24","37","96","04" }, queries = { {2,1},{2,2} };
			auto res = Solution().smallestTrimmedNumbers(nums, queries);
			AssertEx({ 3,0 }, res);
		}
	};

	TEST_CLASS(LC787)
	{
		//LC787. K 站中转内最便宜的航班
		class Solution {
		public:
			int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
				int iMin = INT_MAX / 2;
				vector<int> pre(n, INT_MAX / 2);
				pre[src] = 0;
				auto neiBo = CNeiBo::Three(n, flights, true, 0);
				for (int i = 0; i <= k; i++) {
					vector<int> dp(n, INT_MAX / 2);
					for (int j = 0; j < n; j++) {
						for (const auto& [next, price] : neiBo[j]) {
							dp[next] = min(dp[next], pre[j] + price);
						}
					}
					pre.swap(dp);
					iMin = min(iMin, pre[dst]);
				}
				return iMin >= INT_MAX/2 ? -1 : iMin;
			}
		};
	public:
		int n,   src,  dst,  k;
		vector<vector<int>> edges;
		TEST_METHOD(TestMethod11)
		{
			n = 4, edges = { {0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200} }, src = 0, dst = 3, k = 1;
			auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
			AssertEx(700, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 3, edges = { {0,1,100},{1,2,100},{0,2,500} }, src = 0, dst = 2, k = 1;
			auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
			AssertEx(200, res);
		}
		TEST_METHOD(TestMethod13)
		{
			n = 3, edges = { {0,1,100},{1,2,100},{0,2,500} }, src = 0, dst = 2, k = 0;
			auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
			AssertEx(500, res);
		}
		TEST_METHOD(TestMethod14)
		{
			n = 5, edges = { {1,2,10},{2,0,7},{1,3,8},{4,0,10},{3,4,2},{4,2,10},{0,3,3},{3,1,6},{2,4,5} }, src = 0, dst = 4, k = 1;
			auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
			AssertEx(5, res);
		}
	};	

	TEST_CLASS(LC2321)
	{
		//LC2321. 拼接数组的最大分数
		class Solution {
		public:
			int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
				auto Do = [](vector<int>& nums1, vector<int>& nums2) {
					const int x = accumulate(nums1.begin(), nums1.end(), 0);
					vector<int> nums;
					for (int i = 0; i < nums1.size(); i++) {
						nums.emplace_back(nums2[i] - nums1[i]);
					}
					int pre = 0, sum = 0, ans = INT_MIN;
					for (const auto& i : nums) {
						sum += i;
						pre = min(pre, sum);
						ans = max(ans, sum - pre);
					}
					return x + ans;
				};
				return max(Do(nums1, nums2), Do(nums2, nums1));
			}
		};
	public:
		vector<int> nums1, nums2;
		TEST_METHOD(TestMethod11)
		{
			nums1 = { 60, 60, 60 }, nums2 = { 10, 90, 10 };
			auto res = Solution().maximumsSplicedArray(nums1, nums2);
			AssertEx(210, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums1 = { 20,40,20,70,30 }, nums2 = { 50,20,50,40,20 };
			auto res = Solution().maximumsSplicedArray(nums1, nums2);
			AssertEx(220, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums1 = { 7,11,13 }, nums2 = { 1,1,1};
			auto res = Solution().maximumsSplicedArray(nums1, nums2);
			AssertEx(31, res);
		}

	};

	TEST_CLASS(LC1567)
	{
		//LC1567. 乘积为正数的最长子数组长度
		class Solution {
		public:
			int getMaxLen(vector<int>& nums) {
				int ans = 0,lessCount=0,lessIndex=-1,zeroIndex=-1;
				for (int i = 0; i < nums.size(); i++) {
					if (nums[i] < 0) { 
						lessCount++;
						if (1 == lessCount) {
							lessIndex = i;
						}
					}
					if (0 == nums[i]) {
						zeroIndex = i; 
						lessCount = 0;
					}
					int i1 = zeroIndex;
					if (lessCount & 1) {
						i1 = max(i1, lessIndex);
					}
					ans = max(ans, i - i1);
				}
				return ans;
			}
		};
	public:
		vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, -2, -3, 4 };
			auto res = Solution().getMaxLen(nums);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 0,1,-2,-3,-4 };
			auto res = Solution().getMaxLen(nums);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { -1,-2,-3,0,1 };
			auto res = Solution().getMaxLen(nums);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 5,-20,-20,-39,-5,0,0,0,36,-32,0,-7,-10,-7,21,20,-12,-34,26,2 };
			auto res = Solution().getMaxLen(nums);
			AssertEx(8, res);
		}
	};

	TEST_CLASS(LC2735)
	{
		//LC2735. 收集巧克力
		class Solution {
		public:
			long long minCost(vector<int>& nums, int x) {
				const int N = nums.size();
				vector<vector<int>> vMin(N, vector<int>(N, INT_MAX));
				for (int i = 0; i < N; i++) {
					vMin[i][0] = nums[i];
					for (int j = 1; j < N; j++) {
						vMin[i][j] = min(vMin[i][j - 1], nums[(i + j) % N]);
					}
				}
				long long ans = LLONG_MAX;
				for (int j = 0; j < N; j++) {
					long long cur = (long long)x * j;
					for (int i = 0; i < N; i++) {
						cur += vMin[i][j];
					}
					ans = min(ans, cur);
				}
				return ans;
			}
		};
	public:
		vector<int> nums;
		int x;
		TEST_METHOD(TestMethod11)
		{
			nums = { 20, 1, 15 }, x = 5;
			auto res = Solution().minCost(nums, x);
			AssertEx(13LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,2,3 }, x = 4;
			auto res = Solution().minCost(nums, x);
			AssertEx(6LL, res);
		}	
	};

	TEST_CLASS(LC1224)
	{
		//LC1224. 最大相等频率
		class Solution {
		public:
			int maxEqualFreq(vector<int>& nums) {
				const int iMax = *max_element(nums.begin(), nums.end());
				vector<int> cnt(iMax + 1);
				int iMax1 = 0, iMax2 = 0, cnt1 = 0;
				int ans = 0;
				for (int i = 0; i < nums.size(); i++) {
					auto& t =cnt[nums[i]];
					t++;
					if (1 == t) { cnt1++; }
					if (t > iMax1) {
						iMax1 = t; iMax2 = 1;
					}else if (t == iMax1) {
						iMax2++;
					}
					if ((i == (iMax1 - 1) * cnt1) && (1 == iMax2)) {
						ans = i + 1;
					}
					if (i == iMax1 * iMax2) {
						ans = i + 1;
					}
					if (1 == iMax1) {
						ans = i + 1;
					}
				}
				return ans;
			}
		};
	public:
		vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 2,2,1,1,5,3,3,5 };
			auto res = Solution().maxEqualFreq(nums);
			AssertEx(7, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,1,1,2,2,2,3,3,3,4,4,4,5 };
			auto res = Solution().maxEqualFreq(nums);
			AssertEx(13, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 1,2 };
			auto res = Solution().maxEqualFreq(nums);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 1,1,1 };
			auto res = Solution().maxEqualFreq(nums);
			AssertEx(3, res);
		}
	};

	

	TEST_CLASS(LC3240)
	{
		//LC3240. 最少翻转次数使二进制矩阵回文
		class Solution {
		public:
			int minFlips(vector<vector<int>>& grid) {
				const int R = grid.size();
				const int C = grid[0].size();
				vector<int> pre(4, INT_MAX / 2);
				pre[0] = 0;
				for (int r1 = 0, r2 = R - 1; r1 <= r2; r1++, r2--) {
					for (int c1 = 0, c2 = C - 1; c1 <= c2; c1++, c2--) {
						set<pair<int, int>> cnt = { {r1,c1},{r1,c2},{r2,c1},{r2,c2} };
						int cnt0 = 0, cnt1 = 0;
						for (const auto& [r, c] : cnt) {
							cnt0 += (grid[r][c] == 0);
							cnt1 += (grid[r][c] == 1);
						}
						vector<int> dp(4, INT_MAX / 2);
						for (int p = 0; p < 4; p++) {
							dp[p] = min(dp[p], pre[p] + cnt1);
							dp[(p + cnt.size()) % 4] = min(dp[(p + cnt.size()) % 4],pre[p]+cnt0 );
						}
						pre.swap(dp);
					}
				}
				return pre[0];
			}
		};
	public:
		vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {1,0,0},{0,1,0},{0,0,1} };
			auto res = Solution().minFlips(grid);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {0,1},{0,1},{0,0} };
			auto res = Solution().minFlips(grid);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1},{1} };
			auto res = Solution().minFlips(grid);
			AssertEx(2, res);
		}
	};

	TEST_CLASS(LC2910)
	{
		//LC2910合法分组的最少组数
		class Solution {
		public:
			int minGroupsForValidAssignment(vector<int>& balls) {
				unordered_map<int, int> mCnt;
				for (const auto& n : balls) {
					mCnt[n]++;
				}
				vector<int> cnt;
				for (const auto& [t, c] : mCnt) {
					cnt.emplace_back(c);
				}
				const int m1 = *min_element(cnt.begin(), cnt.end());
				int x = m1;
				for (; x >= 1; x--) {
					bool b = true;
					for (const auto& c : cnt) {
						const int x1 = c / x;
						const int x2 = c % x;
						b &= (x2 <= x1);
					}
					if (b)break;
				}
				int ans = 0;
				for (const auto& c : cnt) {
					const int x1 = c / x;//总盒子的数量
					const int x2 = c % x;//装x+1的盒子数量
					const int x3 = x1 - x2;//装x的盒子数量
					const int x4 = x3 / (lcm(x, x + 1) / x);//将装x的盒子替换为x+1
					ans += c / x - x4 ;
				}
				return ans;
			}
		};
	public:
		vector<int> balls;
		TEST_METHOD(TestMethod11)
		{
			balls = { 3, 2, 3, 2, 3 };
			auto res = Solution().minGroupsForValidAssignment(balls);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			balls = { 10,10,10,3,1,1 };
			auto res = Solution().minGroupsForValidAssignment(balls);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod13)
		{
			balls = { 1,1,3,3,1,1,2,2,3,1,3,2 };
			auto res = Solution().minGroupsForValidAssignment(balls);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod14)
		{
			balls = { 2,1,1,2,2,3,1,3,1,1,1,1,2 };
			auto res = Solution().minGroupsForValidAssignment(balls);
			AssertEx(6, res);
		}
	};

	TEST_CLASS(LC2768)
	{
		//LC2768. 黑格子的数目
		class Solution {
		public:
			vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
				unordered_map<int, unordered_map<int, int>> cnt;
				auto Add = [&](int r, int c) {
					if ((r < 0)||(r+1 ==m ))return;
					if ((c < 0)||(c+1==n)) return;
					cnt[r][c]++;
				};
				for (const auto& v : coordinates) {
					Add(v[0] - 1, v[1] - 1);
					Add(v[0] - 1, v[1] );
					Add(v[0], v[1] - 1);
					Add(v[0], v[1]);
				}
				vector<long long > ans(5);
				ans[0] = (long long)(m-1) * (n-1);
				for (const auto& [t, t2] : cnt) {
					for (const auto& [t3, c] : t2) {
						ans[0]--;
						ans[c]++;
					}
				}
				return ans;
			}
		};
	public:
		int m, n;
		vector<vector<int>> coordinates;
		TEST_METHOD(TestMethod11)
		{
			m = 3, n = 3, coordinates = { {0,0} };
			auto res = Solution().countBlackBlocks(m, n, coordinates);
			AssertEx({ 3,1,0,0,0 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			m = 3, n = 3, coordinates = { {0,0},{1,1},{0,2} };
			auto res = Solution().countBlackBlocks(m, n, coordinates);
			AssertEx({ 0,2,2,0,0 }, res);
		}
	};

	TEST_CLASS(LC906)
	{
		//LC906. 超级回文数
		class Solution {
		public:
			int superpalindromesInRange(string left, string right) {
				static auto xs = XS();
				long long l = atoll(left.c_str());
				long long r = atoll(right.c_str());
				auto Is = [](long long y) {
					string str = to_string(y);
					const int N = str.length();
					for (int i = 0; i < N / 2; i++) {
						if (str[i] != str[N - 1 - i]) { return false; }
					}
					return true;
				};
				int ans = 0;
				for (const auto& x : xs) {
					long long y = (long long)x * x;
					if ((y < l) || (y > r)) { continue; }
					ans += Is(y);
				}
				return ans;
			}
			vector<int> XS() {
				vector<int > ans(10);
				iota(ans.begin(), ans.end(), 0);
				int mul = 1;
				for (int z = 1; z < 10000; z++) {
					int tmp = z;
					int z1 = 0;
					while (tmp > 0) {
						z1 = z1*10+tmp % 10;
						tmp /= 10;
					}
					if (mul == z) {
						mul *= 10;
					}
					ans.emplace_back(z*mul+z1);
					for (int u = 0; u < 10; u++) {
						ans.emplace_back(z * mul * 10 + u * mul + z1);
					}
				}
				return ans;
			}
		};
	public:
		string L,  R;
		TEST_METHOD(TestMethod11)
		{
			L = "4", R = "1000";
			auto res = Solution().superpalindromesInRange(L, R);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			L = "1", R = "2";
			auto res = Solution().superpalindromesInRange(L, R);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			L = "1", R = "999999999999999999";
			auto res = Solution().superpalindromesInRange(L, R);
			AssertEx(70, res);
		}
	};

	TEST_CLASS(LC3306)
	{
		//LC3306. 元音辅音字符串计数 II
		class Solution {
		public:
			long long countOfSubstrings(string word, const int K) {
				string strs = "aoeiu";
				vector<int> v(5, -1);
				vector<int> inxs;
				long long ans = 0;
				for (int i = 0; i < word.size();i++ ) {
					const auto& ch = word[i];
					int type = -1;
					for (int j = 0; j < strs.length(); j++) {
						if (ch == strs[j]) { type = j ; }
					}
					if (-1 == type) { inxs.emplace_back(i); }
					else { v[type] = i; }
					const int iMax1 = *min_element(v.begin(), v.end())+1;
					const int k = inxs.size();		
					if (k < K) { continue; }
					const int i2 = k - K ;
					const int iMax2 = (i2>=k) ? (i+1):( inxs[i2]+1);
					const int iMax = min(iMax1,iMax2 );
					const int i1 = k - K - 1;
					const int iMin = (i1 < 0) ? -1 : inxs[i1];
					const int cur = iMax - iMin - 1;
					ans += max(0, cur);
				}
				return ans;
			}
		};
	public:
		string word;
		int k;
		TEST_METHOD(TestMethod11)
		{
			word = "aeioqq", k = 1;
			auto res = Solution().countOfSubstrings(word, k);
			AssertEx(0LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			word = "aeiou", k = 0;
			auto res = Solution().countOfSubstrings(word, k);
			AssertEx(1LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			word = "ieaouqqieaouqq", k = 1;
			auto res = Solution().countOfSubstrings(word, k);
			AssertEx(3LL, res);
		}
	};

	TEST_CLASS(P12085)
	{
		//【 双向链表+小根堆】P12085 [蓝桥杯 2023 省 B] 整数删除|普及+
		typedef pair<long long, int> T;
		class Solution {
		public:
			vector<long long> Ans(const int K,vector<long long>&a) {
				const int N = a.size();
				list<int> data;
				priority_queue<T, vector<T>, greater<>> valinx;
				vector<list<int>::iterator> vit(N);
				for (int i = 0; i < a.size(); i++) {
					data.emplace_back(i);
					vit[i] = prev(data.end());				
					valinx.emplace(a[i], i);
				}
				for (int i = 0; i < K; i++) {
					while (valinx.top().first != a[valinx.top().second]) {
						const int inx = valinx.top().second;
						valinx.pop();
						valinx.emplace(a[inx], inx);
					}
					const auto[val, inx] = valinx.top();
					valinx.pop();
					auto it = vit[inx];
					if (data.begin() != it) {
						a[*prev(it)] += val;
					}
					auto it2 = next(it);
					if (data.end() != it2) {
						a[*it2] += val;
					}
					a[*it] = -1;
					data.erase(it);
				}
				vector<long long > ans;
				for (int i = 0; i < N; i++) {
					if (a[i] >= 0) {
						ans.emplace_back(a[i]);
					}
				}
				return ans;
			}
		};
	public:
		vector<long long> a;
		int K;
		TEST_METHOD(TestMethod11)
		{
			K = 3, a = { 1,4,2,8,7 };
			auto res = Solution().Ans(K, a);
			AssertV({ 17,7 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			K = 3, a = { 0,0,0,0};
			auto res = Solution().Ans(K, a);
			AssertV({ 0 }, res);
		}
	};

	TEST_CLASS(P12275)
	{
		//P12275 [蓝桥杯 2024 国 Python B] 工厂|普及+
		class Solution {
		public:
			double Ans(const int N,vector<int> price, vector<tuple<int,int,int,int>>& xykw) {
				sort(xykw.begin(), xykw.end(), [&](auto& t1, auto& t2) {return get<1>(t1) < get<1>(t2); });
				vector<double> times(N, 1e100);
				for ( auto [x, y, k, w] : xykw) {
					x--, y--;
					if (0 == k) {
						times[y] = min(times[y], 1.0 / w);
						continue;
					}
					if (times[x] >= 1e100) { continue; }//缺原料
					times[y] = min(times[y], 1.0 / w+ (double)k/w*times[x]);
				}
				double ans = 0;
				for (int i = 0; i < N; i++) {
					ans = max(ans, price[i] / times[i]);
				}
				return ans;
			}
		};
	public:
		int N;
		vector<int> price;
		vector<tuple<int, int, int, int>> xykw;
		TEST_METHOD(TestMethod11)
		{
			N = 3, price = { 1,0,2 }, xykw = { {1,1,0,6},{1,2,5,10},{2,3,6,10} };
			auto res = Solution().Ans(N, price, xykw);
			AssertEx(9.52, res,0.01);
		}
	};

	TEST_CLASS(P9751)
	{
		//【分支界限法】P9751 [CSP-J 2023] 旅游巴士|普及+
		class Solution {
		public:
			int Ans(const int N,const int K,vector<tuple<int, int, int>>& edge) {
				const int iNotMay = 1e9;
				vector<vector<int>> dis(N, vector<int>(K,iNotMay));
				priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
				auto Add = [&](int cur, int t) {
					if (dis[cur][t % K] <= t) {
						return;
					}
					dis[cur][t%K] = t;
					minHeap.emplace(t,cur);
				};
				Add(0, 0);
				auto neiBo = CNeiBo::Three(N, edge, true, 1);
				while (minHeap.size()) {
					const auto [t, cur] = minHeap.top(); minHeap.pop();
					for (const auto& [next, a] : neiBo[cur]) {
						int t1 = t + 1;
						if (t < a) {
							t1 = t+ Ceil(a - t, K)*K+1;
						}
						Add(next, t1);
					}
				}
				const int ans = dis.back()[0];
				if (iNotMay == ans) { return -1; }
				return ans;
			}
			int Ceil(int i1, int i2) {
				return i1 / i2 + (0 != i1 % i2);
			}
		};
	public:
		int N,K;
		vector<tuple<int, int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			N = 5,K=3, edge = { {1,2,0},{2,5,1},{1,3,0},{3,4,3},{4,5,1} };
			auto res = Solution().Ans(N, K,edge);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod12)
		{
			N = 5, K = 3, edge = { {1,2,0},{2,5,1},{1,3,0},{3,4,3},{4,5,1} };
			auto res = Solution().Ans(N, K, edge);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 5, K = 1, edge = { {1,2,0},{2,3,0},{3,4,0},{4,5,0},{1,5,1} };
			auto res = Solution().Ans(N, K, edge);
			AssertEx(2, res);
		}	
	};

	TEST_CLASS(P9670)
	{
		//【模拟】P9670 [ICPC 2022 Jinan R] Frozen Scoreboard|普及+
		class Solution {
		public:
			vector<string> Ans(int rcnt,int time, vector<string>& strs) {
				int n1 = 0, t1 = 0;
				vector<tuple<int, int,int>> v;
				for (const auto& s : strs) {
					if ('+' == s[0]) {
						int pos1 = s.find('/');
						const int x = atoi(s.c_str() + 2);
						const int y = atoi(s.c_str() + pos1 + 1);
						n1++;
						t1 += (x - 1) * 20 + y;
					}
					else if ('?' == s[0]) {
						auto tmp = s.substr(2);
						const int pos = tmp.find(' ');
						const int x = atoi(tmp.c_str() );
						const int y = atoi(tmp.c_str() + pos + 1);
						v.emplace_back(y, y - x + 1,240);
					}
				}
				if (v.empty()) {
					if ((n1 != rcnt) || (time != t1)) { return {};	}
					return strs;
				}				
				const int M = 1 << v.size();
				for (int m = 0; m < M; m++)
				{
					int i = -1;
					int n2 = 0, t21 = 0, t22 = 0;
					for (const auto& [may, miy,tmp] : v) {
						i++;
						if ((1 << i) & m) { continue; }
						n2++;
						t21 += (miy - 1) * 20 + 240;
						t22 += (may - 1) * 20 + 299;
					}
					if ((n1 + n2 != rcnt)) { continue; }
					if ((time < t1 + t21) || (time > t1 + t22)) { continue; }
					int remain = time - t1 - t21;
					i = -1;
					for (auto& [may, miy, tmp] : v) {
						i++;
						if ((1 << i) & m) { continue; }
						const int i1 = min(may - miy, remain / 20);
						miy += i1; remain -= i1 * 20;
					}
					i = -1;
					for (auto& [may, miy, tmp] : v) {
						i++;
						if ((1 << i) & m) { continue; }
						const int i1 = min(59, remain);
						tmp += i1; remain -=i1;
					}
					vector<string> str2;
					i = -1;
					for (auto& [may, miy, tmp] : v) {
						i++;
						if ((1 << i) & m) { str2.emplace_back("- " + to_string(may)); continue; }
						str2.emplace_back("+ " + to_string(miy) +"/" + to_string(tmp));
					}
					for (int i = 0, j = 0; i < strs.size(); i++) {
						if ('?' == strs[i][0]) {
							strs[i] = str2[j++];
						}
					}
					return strs;
				}
				return {};
			}		
		};
	public:
		int rcnt, time;
		vector<string> strs;
		void Check(int rcnt, int time, vector<string> strs) {
			int n1 = 0, t1 = 0;
			for (const auto& s : strs) {
				if ('+' == s[0]) {
					int pos1 = s.find('/');
					const int x = atoi(s.c_str() + 2);
					const int y = atoi(s.c_str() + pos1 + 1);
					n1++;
					t1 += (x - 1) * 20 + y;
				}
			}
			AssertEx(rcnt, n1);
			AssertEx(time, t1);
		}
		TEST_METHOD(TestMethod11)
		{
			rcnt = 7, time = 951, strs = { "+ 1/6","? 3 4","+ 4/183","- 2","+ 3/217",".",".",".","+ 2/29","+ 1/91",".","+ 1/22","."};
			auto res = Solution().Ans(rcnt,time, strs);
			Check(rcnt, time, res);
		}	
		TEST_METHOD(TestMethod12)
		{
			rcnt = 1, time = 100, strs = { ".","? 3 4" };
			auto res = Solution().Ans(rcnt, time, strs);
			AssertEx({}, res);
		}
		TEST_METHOD(TestMethod13)
		{
			rcnt = 2, time = 100, strs = { "+ 1/1","+ 1/2" };
			auto res = Solution().Ans(rcnt, time, strs);
			AssertEx({}, res);
		}
		TEST_METHOD(TestMethod14)
		{
			rcnt = 2, time = 480, strs = { "? 99 100","? 100 100" };
			auto res = Solution().Ans(rcnt, time, strs);
			AssertEx({}, res);
		}
		TEST_METHOD(TestMethod21)
		{
			rcnt = 0, time = 0, strs = { "- 5","- 6" };
			auto res = Solution().Ans(rcnt, time, strs);
			Check(rcnt, time, res);
		}
		TEST_METHOD(TestMethod22)
		{
			rcnt = 2, time = 480, strs = { "? 100 100","? 100 100" };
			auto res = Solution().Ans(rcnt, time, strs);
			Check(rcnt, time, res);
		}
		TEST_METHOD(TestMethod23)
		{
			rcnt = 1, time = 2000, strs = { "? 100 100","? 100 100" };
			auto res = Solution().Ans(rcnt, time, strs);
			Check(rcnt, time, res);
		}
	};

	TEST_CLASS(P9820)
	{
		//【模拟】P9820 [ICPC 2020 Shanghai R] Mine Sweeper II|普及+
		class Solution {
		public:
			vector<string> Ans(vector<string>& A,vector<string>& B) {
				const int R = A.size(), C = A[0].length();
				int sameCnt = 0;
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						sameCnt += (A[r][c] == B[r][c]);
					}
				}
				if (sameCnt <= R * C / 2) {
					vector<string> ans(R,string(C, ' '));
					for (int r = 0; r < R; r++) {
						for (int c = 0; c < C; c++) {
							ans[r][c] = ('.'==A[r][c])?'X':'.';
						}
					}
					return ans;
				}
				return A;
			}
		};
	public:
		vector<string> A, B;
		TEST_METHOD(TestMethod11)
		{
			A = { "X..X","X.X." }, B = { "X.X.",".X.." };
			auto res = Solution().Ans(A,B);			
		}
	};
	TEST_CLASS(P9804)
	{
		//【模拟 双向队列】P9804 [POI 2022 ~2023R1] kol|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, vector<tuple<int, int, int>>& xyc, vector<tuple<char, int, int>>& ope) {
				vector<vector<int>> grid(N, vector<int>(N, -1));
				for (auto& [x, y, c] : xyc) {
					x--, y--;
					grid[x][y] = c;
				}
				deque<pair<int, int>> quePos;//蛇头在前
				vector<int> vVal;//vVal[0]是蛇尾	
				quePos.emplace_back(0, 0); vVal.emplace_back(0);
				map<pair<int, int>,int> mPos;//mPos[x][y]+iMove记录(x,y)是蛇身体的第几部分，头是0。
				mPos[make_pair(0, 0)] = 0;
				int iMove = 0;
				vector<int> ans;
				auto Move = [&](int x, int y) {
					x += quePos.front().first;
					y += quePos.front().second;
					if (min(x, y) < 0) { return; }
					if (max(x, y) >= N) { return; }
					if (-1 != grid[x][y]) {
						quePos.emplace_front(x, y);
						iMove++;
						mPos[make_pair(x, y)] = -iMove;
						vVal.emplace_back(grid[x][y]);
						grid[x][y] = -1;
					}
					else {
						mPos.erase(quePos.back());
						quePos.emplace_front(x, y);
						quePos.pop_back();
						iMove++;
						mPos[make_pair(x, y)] = -iMove;
					}
				};
				for (auto& [kind, x, y] : ope) {
					x--, y--;
					if ('Z' == kind) {
						if (!mPos.count(make_pair(x,y))) {
							ans.emplace_back(-1);
						}
						else {
							const int iPos = mPos[make_pair(x, y)] + iMove;
							ans.emplace_back(vVal[vVal.size()-1-iPos]);
						}
					}
					else if ('G' == kind) {
						Move(- 1, 0);
					}
					else if ('D' == kind) {
						Move(1, 0);
					}
					else if ('L' == kind) {
						Move(0,  - 1);
					}
					else if ('P' == kind) {
						Move(0,  1);
					}
					else {
						assert(false);
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<tuple<int, int, int>> xyc;
		vector<tuple<char, int, int>> ope;
		TEST_METHOD(TestMethod11)
		{
			N = 6, xyc = { {1,3,1},{5,1,5},{2,3,2},{3,4,1},{3,5,3} }, ope = { {'Z',1,1},{'Z',1,2},{'P',
0,0},{'P',0,0},{'D',0,0},{'D',0,0},{'P',0,0},{'Z',3,5},{'P',0,0},{'Z',3,5},{'D',0,0},{'Z',3,5},{'L',0,0},{'Z',3,5} };
			auto res = Solution().Ans(N, xyc, ope);
			AssertV({ 0,-1,-1,3,1,2 }, res);
		}
	};
	TEST_CLASS(P10692)
	{
		//P10692 [SNCPC2024] 表达式矩阵|普及+
		class Solution {
		public:
			vector<string> Ans(const int R,const int C ) {
				vector<string> ans(R, string(C, '1'));
				for(int r = 1; r+1 < R;r++)
					for (int c = 1; c + 1 < C; c++) {
						if (0 == (r + c) % 2) {
							ans[r][c] = '*';
						}
					}
				if ((C & 1) && (C > 3)) {
					for (int r = 2; r + 1 < R; r+=2) {
						const int c = (r + 1 < C) ? r : 2;
						ans[r][c] = '+';
					}
				}
				if ((R & 1) && (R > 3)) {
					for (int c = 2; c + 1 < C; c+=2) {
						const int r = (c + 1 < R) ? c : 2;
						ans[r][c] = '+';
					}
				}
				return ans;
			}
		};
	public:
		void Check(int R,int C,vector<string>& strs) {
			string b[10][10];
			b[3][3] = "1111*1111";
			b[3][4] = "11111*111111";
			b[3][5] = "111111*1*111111";
			b[3][6] = "1111111*1*11111111";
			b[3][7] = "11111111*1*1*11111111";
			b[3][8] = "111111111*1*1*1111111111";
			b[3][9] = "1111111111*1*1*1*1111111111";
			b[4][3] = "1111111*1111",
				b[4][4] = "11111*1111*11111";
			b[4][5] = "111111*1*111+1111111";
			b[4][6] = "11111111*1*11*1*11111111";
			b[4][7] = "11111111*1*1*111+1*111111111";
			b[4][8] = "111111111*1*1*1111*1*1*111111111";
			b[4][9] = "1111111111*1*1*1*111*1*1+11111111111";
			b[5][3] = "1111*11111*1111",
				b[5][4] = "11111*1111+11*111111",
				b[5][5] = "111111*1*111+111*1*111111";
			b[5][6] = "1111111*1*1111+1+11*1*11111111";
			b[5][7] = "11111111*1*1*111+1+111*1*1*11111111";
			b[5][8] = "111111111*1*1*1111+1+1+11*1*1*1111111111";
			b[5][9] = "1111111111*1*1*1*111+1+1+111*1*1*1*1111111111";
			b[6][3] = "1111111*11111*1111",
				b[6][4] = "11111*1111*11*1111*11111",
				b[6][5] = "1111111+111*1*111+111*1*111111",
				b[6][6] = "1111111*1*1111*1*11*1*1111*1*1111111";
			b[6][7] = "11111111*1*1*111+1*111*1*1*111+1*111111111";
			b[6][8] = "111111111*1*1*1111*1*1*11*1*1*1111*1*1*111111111";
			b[6][9] = "1111111111*1*1*1*111*1*1+111*1*1*1*111+1*1*11111111111";
			b[7][3] = "1111*11111*11111*1111",
				b[7][4] = "11111*1111*11*1111+11*111111",
				b[7][5] = "111111*1*111+111*1*111+111*1*111111",
				b[7][6] = "1111111*1*1111*1*11*1*1111+1+11*1*11111111",
				b[7][7] = "11111111*1*1*111+1*111*1*1*111*1+111*1*1*11111111";
			b[7][8] = "111111111*1*1*1111+1*1+11*1*1*1111*1+1*11*1*1*1111111111";
			b[7][9] = "1111111111*1*1*1*111*1*1+111*1*1*1*111+1+1*111*1*1*1*1111111111";
			b[8][3] = "1111111*11111*11111*1111";
			b[8][4] = "111111*11*1111*11*1111*11*111111",
				b[8][5] = "1111111+111*1*111+111*1*111+111*1*111111",
				b[8][6] = "11111111*1*11*1*1111*1*11*1*1111*1*11*1*11111111",
				b[8][7] = "111111111+1*111*1*1*111*1+111*1*1*111+1*111*1*1*11111111",
				b[8][8] = "111111111*1*1*1111*1*1*11*1*1*1111*1*1*11*1*1*1111*1*1*111111111";
			b[8][9] = "1111111111*1*1*1*111+1*1*111*1*1*1*111+1*1*111*1*1*1*111*1*1+11111111111";
			b[9][3] = "1111*11111*11111*11111*1111";
			b[9][4] = "11111*1111+11*1111*11*1111*11*111111",
				b[9][5] = "111111*1*111+111*1*111+111*1*111+111*1*111111",
				b[9][6] = "1111111*1*1111+1*11*1*1111*1*11*1*1111*1+11*1*11111111",
				b[9][7] = "11111111*1*1*111+1*111*1*1*111*1+111*1*1*111*1+111*1*1*11111111",
				b[9][8] = "111111111*1*1*1111*1*1+11*1*1*1111*1*1*11*1*1*1111+1+1*11*1*1*1111111111",
				b[9][9] = "1111111111*1*1*1*111+1*1*111*1*1*1*111*1+1*111*1*1*1*111*1*1+111*1*1*1*1111111111";
			int c1=0, c2=0, d1=0, d2=0;
			for (auto& s : strs) {
				for (const auto& ch : s) {
					c1 += ('+' == ch);
					c2 += ('*'==ch);
				}
			}
			for (const auto& ch : b[R][C]) {
				d1 += ('+' == ch);
				d2 += ('*' == ch);
			}
			wstring str = to_wstring(R) + L"C" + to_wstring(C);;
			Assert::AreEqual(d1, c1, str.c_str());
			Assert::AreEqual(d2, c2, str.c_str());
		}
		TEST_METHOD(TestMethod11)
		{			
			auto res = Solution().Ans(3,3);
			AssertV({ "111","1*1","111"}, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().Ans(4, 3);
			AssertV({ "111","1*1","111","111" }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().Ans(3,4);
			AssertV({ "1111","1*11","1111" }, res);
		}
		TEST_METHOD(TestMethod14)
		{
			for(int r =3 ;r <= 9;r++)
				for (int c = 3; c <= 9; c++)
				{
					auto res = Solution().Ans(r, c);
					Check(r, c, res);
				}
		}
	};

	TEST_CLASS(P10361)
	{
		//【逆向思考】P10361 [PA 2024] Łamigłówka 3|普及+
		class Solution {
		public:
			vector<tuple<bool,int,char>> Ans(vector<string>& strs) {
				const int R = strs.size(), C = strs[0].size();
				vector<vector<int>> rows(R,vector<int>(26)),cols(C, vector<int>(26));
				vector<int> rowColorCnt(R), colColorCnt(C);
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						rows[r][strs[r][c]-'A']++;
						cols[c][strs[r][c] - 'A']++;
					}
				}
				vector<tuple<bool, int, char>> ans;
				auto CheckRow = [&](int r) {					
					if (1 == rowColorCnt[r]) {
						for (int i = 0; i < 26; i++) {
							if (rows[r][i] > 0) {
								ans.emplace_back(true, r, 'A' + i);
								rows[r][i] = 0;
								rowColorCnt[r] = 0;
							}
						}		
					}
				};
				auto DelCol = [&](char ch) {
					for (int r = 0; r < R; r++) {
						if (0 == rowColorCnt[r]) { continue; }
						auto& rs = rows[r];
						auto& cnt = rs[ch - 'A'];
						cnt--;
						if (0 == cnt) {
							rowColorCnt[r]--;
						}
						CheckRow(r);
					}
				};
				auto CheckCol = [&](int c) {
					if (1 == colColorCnt[c]) {
						for (int i = 0; i < 26; i++) {
							if (cols[c][i] > 0) {
								ans.emplace_back(false,c, 'A' + i);
								cols[c][i] = 0;
								colColorCnt[c] = 0;
							}
						}
					}
				};
				auto DelRow = [&](char ch) {
					for (int c = 0; c < C; c++) {
						if (0 == colColorCnt[c]) { continue; }
						auto& cs = cols[c];
						auto& cnt = cs[ch - 'A'];
						cnt--;
						if (0 == cnt) {
							colColorCnt[c]--;
						}
						CheckCol(c);
					}
				};
				for (int r = 0; r < R; r++) {
					for (int i = 0; i < 26; i++) {
						rowColorCnt[r] += (rows[r][i] != 0);
					}
					CheckRow(r);
				}
				for (int c = 0; c < C; c++) {
					for (int i = 0; i < 26; i++) {
						colColorCnt[c] += (cols[c][i] != 0);
					}
					CheckCol(c);
				}
				
				for (int i = 0; i < ans.size(); i++) {
					const auto& [b, rc, ch] = ans[i];
					if (b) {
						DelRow(ch);
					}
					else {
						DelCol( ch);
					}
				}
				return vector<tuple<bool,int,char>>(ans.rbegin(),ans.rend());
			}
		};
	public:
		vector<string> strs;
		void Check(const vector<string>& strs, const vector<tuple<bool, int, char>>& res) {			
			const int R = strs.size(), C = strs[0].size();
			assert(res.size() <= R + C);
			vector<string> strs2(R, string(C, '?'));
			for (const auto& [b, rc, ch] : res) {
				if (b) {
					strs2[rc].assign(C, ch);
				}
				else {
					for (int r = 0; r < R; r++) {
						strs2[r][rc] = ch;
					}
				}
			}
			AssertV(strs, strs2);
		//	wstring str = to_wstring(R) + L"C" + to_wstring(C);;
			//Assert::AreEqual(d1, c1, str.c_str());
		//	Assert::AreEqual(d2, c2, str.c_str());
		}
		TEST_METHOD(TestMethod11)
		{
			strs = { "AAPAA","APPAA","AAPAA","AAPAA","APPPA" };
			auto res = Solution().Ans(strs);
			Check(strs, res);
		}
		TEST_METHOD(TestMethod12)
		{
			strs = { "AAA","PPP" };
			auto res = Solution().Ans(strs);
			Check(strs, res);
		}
		TEST_METHOD(TestMethod13)
		{
			strs = { "AAA","BCD","BCD"};
			auto res = Solution().Ans(strs);
			Check(strs, res);
		}
	};

	TEST_CLASS(P10816)
	{
		//超时 P10816 [EC Final 2020] Namomo Subsequence|普及+
		
		typedef	C1097Int<998244353> BI;
		class Solution {
		public:				
			Solution(const string& s) {	
				
				auto start = high_resolution_clock::now();
				const int N = s.length();
				vector<char> v;
				for (int i = 0; i < 26; i++) {
					v.emplace_back('a' + i);		
				}
				for (int i = 0; i < 26; i++) {
					v.emplace_back('A' + i);
				}
				for (int i = 0; i < 10; i++) {
					v.emplace_back('0' + i);
				}
				int code[256] = { 0 };
				for (int i = 0; i < v.size(); i++) {
					code[v[i]] = i;
				}
				m_v.resize(N);
				for (int i = 0; i < N;i++) {
					m_v[i] = code[s[i]];
				}				
				m_iN = v.size();	
				m_cnt.assign(m_iN,0);
				cnt2.assign(m_iN, vector<int>(m_iN)); 
				cnt3.assign(m_iN, vector<int>(m_iN)); 

				m_preSqualSum.assign(m_iN, vector<long long>(N + 1));
				m_preSqualSums.assign(N + 1, 0);
				m_preCnt.assign(m_iN, vector<int>(N + 1));
				vector<int> cnt(m_iN);
				for (int i = 0; i < N; i++) {
					cnt[m_v[i]]++;
					m_preSqualSum[m_v[i]][i+ 1] = cnt[m_v[i]] * (cnt[m_v[i]] - 1) / 2;
				}
				for (int i = 1; i <= N; i++) {
					for (int j = 0; j < m_iN; j++) {
						m_preSqualSum[j][i] = max(m_preSqualSum[j][i], m_preSqualSum[j][i - 1]);
						m_preSqualSums[i] += m_preSqualSum[j][i];
						m_preCnt[j][i] = m_preCnt[j][i - 1] + (j == m_v[i - 1]);
					}
				}

				auto end = high_resolution_clock::now();
				auto duration = duration_cast<milliseconds>(end - start);
				if (duration.count() > 500) {
					throw("dd");
				}
			}
			int Ans() {				
				BI ans;
				const int N = m_v.size();				
				for (int i = N - 1; i >= 0; i--) {					
					for (int j = 0; j < m_iN; j++) {
						if (m_v[i] == j) { continue; }
						cnt2[m_v[i]][j] += m_cnt[j];
						DoMod(cnt2[m_v[i]][j]);
						cnt3[m_v[i]][j] += cnt2[j][m_v[i]];	
						DoMod(cnt3[m_v[i]][j]);
						long long preCnt =i- m_preCnt[j][i]- m_preCnt[m_v[i]][i];
						preCnt = preCnt * (preCnt - 1) / 2 - (m_preSqualSums[i] - m_preSqualSum[m_v[i]][i] - m_preSqualSum[j][i]);
						ans += (preCnt %MOD * cnt3[j][m_v[i]])%MOD;
					}
					m_cnt[m_v[i]]+=1;
				}
				return ans.ToInt();
			}	
			void DoMod(int& x) {				
				if (x > MOD) { x -= MOD; }
			}
			const int MOD = 998244353;
			vector<int> m_v;
			int m_iN;	
			vector<vector<int>> cnt2, cnt3;
			vector<int> m_cnt;
			vector<vector<long long>> m_preSqualSum;
			vector<long long> m_preSqualSums;
			vector<vector<int>> m_preCnt;
		};
	public:
		
	TEST_METHOD(TestMethod11)
		{
			auto res = Solution("abcdcd").Ans();
			AssertEx(1, res);
		}
	TEST_METHOD(TestMethod12)
	{
		auto res = Solution("adbcdcd").Ans();
		AssertEx(1, res);
	}
	TEST_METHOD(TestMethod13)
	{
		auto res = Solution("gshfd1jkhaRaadfglkjerVcvuy0gf").Ans();
		AssertEx(73, res);
	}
	TEST_METHOD(TestMethod14)
	{
		auto res = Solution("retiredMiFaFa0v0").Ans();
		AssertEx(33, res);
	}
	TEST_METHOD(TestMethod15)
	{
		auto res = Solution("aabcdcd").Ans();
		AssertEx(2, res);
	}
	TEST_METHOD(TestMethod16)
	{
		auto res = Solution("aabddd2Aczdcdzd").Ans();
		AssertEx(88, res);
	}
	TEST_METHOD(TestMethod17)
	{
		auto res = Solution("aabxx3d32zdddddddxxx3d32ddaxxx3d322bdesxxdddxx3d32sdddddxxxxd3xxxd32222467890xxxd322d2AczfAABBBCDDxxxd322DDDDDxxxd3xxxd32222DDDfffdcsdddzd").Ans();
		AssertEx(23578825, res);
	}
	TEST_METHOD(TestMethod18)
	{
		auto res = Solution("abcddcd").Ans();
		AssertEx(2, res);
	}
	};

	TEST_CLASS(P10990)
	{
		//【完全二叉树】 P10990 [蓝桥杯 2023 国 Python A] 彩色二叉树|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, vector<tuple<int, int, int>>& ope) {
				const int M = 20;
				vector<vector<pair<int,int>>> cols(N + 1, vector<pair<int,int>>(M, { -1,0 }));
				auto F = [&](int x, int y, int z,int time) {
					for (int i = 0; i <= min(y,M-1); i++) {
						cols[x][i] = { time,z };
					}
				};
				int time = -1;
				auto G = [&](int x, int y, int z) {
					time++;
					while (x) {
						F(x, y, z, time);
						x /= 2; y--;
					}
					
				};
				auto Que = [&](int x) {
					pair<int, int> ans{ -1,0 };
					int y = 0;
					while (x) {
						ans = max(ans, cols[x][y]);
						x /= 2; y++;
					}
					return ans.second;
				};
				vector<int> ans;
				for (const auto& [x, y, z] : ope) {
					if (-1 == y) {
						ans.emplace_back(Que(x));
					}
					else {
						G(x, y, z);
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<tuple<int, int, int>> ope;
		TEST_METHOD(TestMethod11)
		{
			N = 6, ope = { {1,1,1},{3,-1,-1},{5,2,2},{4,-1,-1},{1,-1,-1},{3,-1,-1} };
			auto res = Solution().Ans(N,ope);
			AssertEx({ 1,2,2,1 }, res);
		}	
	};

	TEST_CLASS(P10032)
	{
		//【ad-hoc mex】P10032 「Cfz Round 3」Mex of Sequence|普及+
		class Solution {
		public:
			vector<int> Ans(int M, vector<int>& A) {
				const int N = A.size();
				if (M > 1) {
					if (M & 1) { M = 3; }
					else {
						M = 2;
					}
				}
				vector<int> pre = A;
				while (M--) {
					vector<int> cnt(N);
					for (const auto& i : pre) {
						if (i < N) {
							cnt[i]++;
						}
					}
					int mex = N;
					for (int i = 0; i < N; i++) {
						if (0 == cnt[i]) { mex = i; break; }
					}
					for (auto& i : pre) {
						if ((i > mex) || (cnt[i] > 1)) {
							i = mex;
						}
					}
				}
				return pre;
			}
		};
	public:
		int M;
		vector<int> A;
		TEST_METHOD(TestMethod11)
		{
			M = 1, A = { 1,0,1,2 };
			auto res = Solution().Ans(M,A);
			AssertV({ 3,0,3,2 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			M = 5, A = { 9,9,6,1 };
			auto res = Solution().Ans(M, A);
			AssertV({ 0,0,0,0 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			M = 5, A = { 1,3,0 };
			auto res = Solution().Ans(M, A);
			AssertV({1,2,0 }, res);
		}
	};

	

	TEST_CLASS(P2407)
	{
		//P2407 [SDOI2009] 地图复原|省选-
		class Solution {
		public:
			vector<string> Ans(vector<string>& strs) {
				const int R = strs.size(), C = strs.front().size();
				vector<string> ans(2 * R - 1, string(2 * C - 1, ' '));
				vector<vector<int>> rows(R), cols(C);
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						ans[2 * r][2 * c] = 'o';
						if ('T' == strs[r][c]) {
							rows[r].emplace_back(c);
							cols[c].emplace_back(r);
						}
					}
				}
				for (int r = 0; r < R; r++) {
					for (int i = 0; i < rows[r].size(); i += 2) {
						for (int c = rows[r][i]; c < rows[r][i + 1]; c++) {
							ans[2 * r][2 * c + 1] = '-';
						}
					}
				}
				for (int c = 0; c < C; c++)
				{
					for (int i = 0; i <cols[c].size(); i += 2) {
						for (int r = cols[c][i]; r < cols[c][i + 1]; r++) {
							ans[2 * r + 1][2 * c] = '|';
						}
					}
				}
				return ans;
			}
		};
	public:
		vector<string> strs;
		TEST_METHOD(TestMethod11)
		{
			strs = { "TST.","S.TT","TSST" };
			auto res = Solution().Ans(strs);
			AssertV({"o-o-o o",
				     "|   |  ",
				     "o o o-o",
					 "|     |" ,
					 "o-o-o-o"}, res);
		}
	};

	TEST_CLASS(LC3261)
	{
		//Q4. 统计满足 K 约束的子字符串数量 II©leetcode
		class Solution {
		public:
			vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
				const int N = s.length();
				vector<int> vMaxR(N, N);//s[i...vMaxR[i]]不是可约束,s[i...vMaxR[i]-1]是k约束。vMaxR升序	
				for (int left = 0,r=0,cnt0=0,cnt1=0; left < N; left++) {
					while (r < N) {
						const int cnt00 = cnt0 + ('0' == s[r]);
						const int cnt11 = cnt1 + ('1' == s[r]);
						if ((cnt00 > k) && (cnt11 > k)) { break; }
						cnt0=cnt00,cnt1=cnt11, r++;
					} 
					vMaxR[left] = r;
					cnt0 -= ('0' == s[left]);
					cnt1 -= ('1' == s[left]);
				}
				vector<long long> preSum = { 0 };
				for (int i = 0; i < N;i++) {
					preSum.emplace_back(preSum.back() + vMaxR[i]-i);
				}
				vector<long long> ans;
				for (const auto& v : queries) {
					long long left2 = lower_bound(vMaxR.begin(), vMaxR.end(), v[1] + 1)-vMaxR.begin();
					long long cur = 0;
					if (left2 <= v[1]) {
						left2 = max(left2, (long long)v[0]);
						cur = ((v[1] - left2 + 1) + 1LL) * (v[1] - left2 + 1) / 2;
						cur += preSum[left2] - preSum[v[0]];
					}
					else {
						cur = preSum[v[1] + 1] - preSum[v[0]];
					}
					ans.emplace_back(cur);
				}
				return ans;
			}
		}; 
	public:
		string s;
		int k;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			s = "0001111", k = 2, queries = { {0,6} };
			auto res = Solution().countKConstraintSubstrings(s,k,queries);
			AssertV({ 26 },res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "010101", k = 1, queries = { {0,5},{1,4},{2,3} };
			auto res = Solution().countKConstraintSubstrings(s, k, queries);
			AssertV({ 15,9,3 }, res);
		}

	};
	TEST_CLASS(LC3260)
	{
		//Q3. 找出最大的 N 位 K 回文数©leetcode
		class Solution {
		public:
			string largestPalindrome(int N, int K) {
				vector<int> unit(N,1);
				for (int i = 1; i < N; i++) {
					unit[i] = unit[i - 1] * 10 % K;
				}
				int iMax = accumulate(unit.begin(), unit.end(), 0) * 9 % K;
				string ans(N, '9');
				if (0 == iMax) { return ans; }
				vector<pair<int,int>> subs[10];
				subs[0] = { { 0,0} };
				auto Change = [&](int i, int change1) {
					for (int j = 1; j < 10; j++) {
						for (int k = 0; k < K; k++)
						{
							if (subs[k].empty()) { continue; }
							const int cur = (change1 * j + k) % K;
							if (subs[cur].size()) { continue; }
							subs[cur] = subs[k];
							subs[cur].emplace_back(i, j);
							if (N - 1 - i != i) {
								subs[cur].emplace_back(N-1-i, j);
							}
						}
					}
				};
				for (int i = (N + 1) / 2 - 1; i >=0; i--) {
					 int change1 = unit[i] ;
					 if (N - 1 - i != i) {
						change1 += unit[N - 1 - i];
					 }
					Change(i, change1);
					if (subs[iMax].size()) {
						for (const auto& [i, sub] : subs[iMax]) {
							ans[i] -= sub;
						}
						return ans;
					}
				}
				return "";
			}
		}; 
	public:
		string s;
		int k;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{			
			auto res = Solution().largestPalindrome(3, 5);
			AssertEx(string("595"), res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().largestPalindrome(1, 4);
			AssertEx(string("8"), res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().largestPalindrome(5, 6);
			AssertEx(string("89898"), res);
		}
	};
	TEST_CLASS(LC3267)
	{
		//3267. 统计近似相等数对 II
		class Solution {
		public:
			int countPairs(vector<int>& nums) {
				int unit[7] = { 1 };
				for (int i = 1; i < 7; i++) { unit[i] = unit[i-1]*10; }
				int cnt = 0;
				unordered_map<int,bitset<5000>> can;
				for (int inx =0;inx < nums.size();inx++) {
					const auto& num = nums[inx];
					can[num].set(inx);
					vector<int> v;
					for (int i = 0,tmp=num; i < 7; i++) {
						v.emplace_back(tmp % 10);
						tmp /= 10;
					}
					unordered_set<int> sNeiBo = { num };
					for (int i = 0; i < 7; i++) {
						for (int j = 0; j < 7; j++) {
							auto tmp = num + (v[i] - v[j]) * unit[j] + (v[j] - v[i]) * unit[i];;
							can[tmp].set(inx);
							sNeiBo.emplace(tmp);
						}
					}
					bitset<5000> has;
					for (const auto& i : sNeiBo) {
						has |= can[i];
					}
					cnt += has.count() - 1;
				}
				return cnt;

			}
		}; 
	public:
		vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1023, 2310, 2130, 213 };
			auto res = Solution().countPairs(nums);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1, 10, 100 };
			auto res = Solution().countPairs(nums);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 9999999,9999999 };
			auto res = Solution().countPairs(nums);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 9999999,9999999,9999999 };
			auto res = Solution().countPairs(nums);
			AssertEx(3, res);
		}
	};
	TEST_CLASS(LC3266)
	{
		//3266. K 次乘运算后的最终数组 II
		class Solution {
		public:
			vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
				if (1 == multiplier) { return nums; }
				const int N = nums.size();
				//若干次后，最小值乘以 mul 后大于 最大值。余下的次数在各数之间平均分配
				priority_queue<pair<long long, int>,vector<pair<long long, int>>,greater<>> minHeap;
				long long llMax = 0;
				for (int i = 0; i < nums.size(); i++) {
					minHeap.emplace(nums[i],i);
					llMax = max(llMax, (long long)nums[i]);
				}
				for (; k && (minHeap.top().first* multiplier <= llMax); k--) {
					auto [val, inx] = minHeap.top();
					minHeap.pop();
					val *= multiplier;
					llMax = max(llMax, val);
					minHeap.emplace(val, inx);
				}
				const int k1 = k / N;
				int k2 = k % N;
				C1097Int<> bi2 = C1097Int<>(multiplier).pow(k1);
				auto bi1 = bi2 * multiplier;
				vector<int> ans(N);
				while (minHeap.size()) {
					const auto [val, inx] = minHeap.top();
					auto cur = (k2 > 0) ? bi1 : bi2; k2--;
					ans[inx] = (cur * val).ToInt();
					minHeap.pop();
				}
				return ans;
			}
		};
	public:
		vector<int> nums;
		int k, multiplier;
		TEST_METHOD(TestMethod11)
		{
			nums = { 2, 1, 3, 5, 6 }, k = 5, multiplier = 2;
			auto res = Solution().getFinalState(nums, k, multiplier);
			AssertEx({ 8,4,6,5,6 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 100000, 2000 }, k = 2, multiplier = 1000000;
			auto res = Solution().getFinalState(nums, k, multiplier);
			AssertEx({ 999999307,999999993 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 2, 4 }, k = 2, multiplier = 2;
			auto res = Solution().getFinalState(nums, k, multiplier);
			AssertEx({ 8,4 }, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 2,1 }, k =3, multiplier =10;
			auto res = Solution().getFinalState(nums, k, multiplier);
			AssertEx({20,100 }, res);
		}
		TEST_METHOD(TestMethod15)
		{
			nums = { 1 }, k = 1000000000, multiplier = 1;
			auto res = Solution().getFinalState(nums, k, multiplier);
			AssertEx({ 1 }, res);
		}
		TEST_METHOD(TestMethod16)
		{
			nums = {100, 1 }, k = 1000000000, multiplier = 1;
			auto res = Solution().getFinalState(nums, k, multiplier);
			AssertEx({ 100,1 }, res);
		}
	};
	TEST_CLASS(LC3646)
	{
		//3266. K 次乘运算后的最终数组 II
		class CTest {
		public:
			int Init(int m ) {				
				for (int j = 0; j < 9; j++) {
					if ((1 << j) & m) {
						const int num = j + 1;	
						m_str += string(num / 2, '0' + num);
						if (num & 1) {
							if (-1 != m_oddNum) { return -1 ; }
							m_oddNum = num;
						}
					}
				}
				return Cnt();
			}
			string Mid()const { return (-1 == m_oddNum) ? "" : string(1, m_oddNum + '0'); }
			int Cnt()const { return m_str.size() * 2 + (-1 != m_oddNum); }
			string m_str;
			int  m_oddNum = -1;
		};
		class Solution {
		public:
			long long specialPalindrome(long long n) {
				string strN = to_string(n);	
				string ans(strN.length(),'A'),ans2(strN.length()+1, 'A');
				auto Add11 = [&](const string& s) {
					if (s <= strN) { return; }
					if (s >= ans) { return; }
					ans = s;
				};
				auto Add1 = [&](const CTest& test) {
					string tmp = test.m_str;
					do
					{
						Add11(tmp + test.Mid() + string(tmp.rbegin(), tmp.rend()));
					} while (std::next_permutation(tmp.begin(), tmp.end()));
				};
				auto Add2 = [&](const CTest& test)
				{
					string tmp = test.m_str;					
					tmp = tmp + test.Mid() + string(tmp.rbegin(), tmp.rend());
					if (tmp < ans2) { ans2 = tmp; }
				};
				const int MC = 1 << 9;
				for (int m = 0; m < MC; m++) {
					CTest test;
					const auto cnt = test.Init(m);
					if (strN.length() == cnt) {
						Add1(test);
					}
					else if (strN.length() + 1 == cnt) {
						Add2(test);
					}
				}
				if (ans.back() == 'A') { ans = ans2; }
				return atoll(ans.c_str());
			}
		}; 
	public:		
		TEST_METHOD(TestMethod11)
		{			
			auto res = Solution().specialPalindrome(2);
			AssertEx(22LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().specialPalindrome(33);
			AssertEx(212LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().specialPalindrome(1000);
			AssertEx(4444LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			auto res = Solution().specialPalindrome(271201);
			AssertEx(424424LL, res);
		}
	};

	TEST_CLASS(LC3655)
	{
		//【分块 差分数组 逆元】3655区间乘法查询后的异或 II|分数未知
		class Solution {
		public:
			int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
				typedef C1097Int<> BI;
				const int N = nums.size();
				vector<BI> bn(nums.begin(),nums.end());				;
				const int K = sqrt(N);
				vector<vector<BI>> diff(K, vector<BI>(N,1));
				for (auto& v : queries) {
					if (v[2] >= K) {
						for (int i = v[0]; i <= v[1]; i += v[2]) {
							bn[i] *= v[3];
						}
					}
					else {
						const int len = (v[1] - v[0]) / v[2] + 1;
						const int rr = v[0] + v[2] * len;
						diff[v[2]][v[0]] *= v[3];
						if (rr < N) {
							diff[v[2]][rr] /= v[3];
						}
					}
				}
				for (int k = 0; k < K; k++) {
					for (int k1 = 0; k1 < k; k1++) {
						BI tmp = 1;
						for (int k2 = k1; k2 < N; k2 += k) {
							tmp *= diff[k][k2];
							bn[k2] *= tmp;
						}
					}
				}
				int ans = 0;
				for (auto& bi : bn) {
					ans ^= bi.ToInt();
				}
				return ans;
			}
		};
	public:
		vector<int> nums;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1,1,1 }, queries = { {0,2,1,4} };
			auto res = Solution().xorAfterQueries(nums, queries);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 2,3,1,5,4 }, queries = { {1,4,2,3},{0,2,1,2} };
			auto res = Solution().xorAfterQueries(nums, queries);
			AssertEx(31, res);
		}
	
	};

	TEST_CLASS(LC3445)
	{
		//【前缀减前缀 】3445. 奇偶频次间的最大差值 II|2694
		class Solution {
		public:
			int maxDifference(string s, int K) {
				const int N = s.length();
				int ans = -100'000;
				auto Do = [&](char a, char b) {
					vector<tuple<int, int, int>> pre = { {0,0,0} };
					int j = 0;
					vector<int> preMin(4, 100'000);
					for (const auto& ch : s) {
						auto [ca, cb, t] = pre.back();
						if (ch == a) {
							ca++; t ^= 1;
						}
						if (ch == b) {
							cb++; t ^= 3;
						}
						while ((pre.size() - j >= K) && (cb > get<1>(pre[j]))) {		
							auto [ca1, cb1, t1] = pre[j];
							preMin[t1] = min(preMin[t1], ca1 -cb1);
							j++;
						}
						ans = max(ans, ca - cb - preMin[t ^ 1]);
						pre.emplace_back(ca, cb, t);
					}
				};
				for (int a = 0; a <= 4; a++) {
					for (int b = 0; b <= 4; b++) {
						Do('0' + a, '0' + b);
					}
				}
				return ans;
			}
		};
	public:
		string s;
		int k;
		TEST_METHOD(TestMethod11)
		{
			s = "12233", k = 4;
			auto res = Solution().maxDifference(s, k);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "1122211", k = 3;
			auto res = Solution().maxDifference(s, k);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "110", k = 3;
			auto res = Solution().maxDifference(s, k);
			AssertEx(-1, res);
		}
	};

	TEST_CLASS(LC3661)
	{
		//【离散化 线段树】3661可以被机器人摧毁的最大墙壁数目|分数未知
		class Solution {
		public:
			int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
				const int N = robots.size();
				const int M = int(1e9 + 1e5 + 1);
				sort(walls.begin(), walls.end());
				vector<pair<int, int>> rd;
				for (int i = 0; i < N; i++) {
					rd.emplace_back(robots[i], distance[i]);
				}
				rd.emplace_back(INT_MIN / 2, 0);
				rd.emplace_back(INT_MAX / 2, 0);
				sort(rd.begin(), rd.end());
				vector<int> vLeft(N+2), vRight(N+2);
				for (int i = 0; i < rd.size(); i++) {
					const auto& [pos, dis] = rd[i];
					const int iLeftRobot = i ? rd[i - 1].first : -M;
					vLeft[i] = max(iLeftRobot, pos - dis-1);
					const int iRightRobot = (i + 1 == N+2) ? M : rd[i + 1].first;
					vRight[i] = min(iRightRobot, pos + dis+1);
				}
				auto Cnt = [&](int left, int r) {
					int ans = lower_bound(walls.begin(), walls.end(), r)- upper_bound(walls.begin(), walls.end(), left);
					return ans;
				};//（left,r)之间的墙数量，不包括left,r。
				vector<int> dp0(N + 2), dp1(N + 2);
				for (int n = 1; n <= N; n++) {
					dp1[n] = max(dp0[n - 1], dp1[n - 1]) + Cnt(rd[n].first,vRight[n]);
					const int g = Cnt(vLeft[n], rd[n].first);
					dp0[n] = dp0[n-1] + g;
					const int iRepeat =  g + Cnt(rd[n-1].first,vRight[n-1])- Cnt(rd[n - 1].first, rd[n].first);
					dp0[n] = max(dp0[n], dp1[n - 1] + g - max(0,iRepeat));
				}
				int cntSamePos = 0;
				for (const auto& pos : robots) {
					cntSamePos += Cnt(pos-1, pos+1);
				}
				return cntSamePos+max(dp0[N], dp1[N]);
			}
		};
		vector<int> robots, distance, walls;
		TEST_METHOD(TestMethod00)
		{
			robots = { 4,10 }, distance = { 3,3 }, walls = { 6,7,8 };
			auto res = Solution().maxWalls(robots, distance, walls);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod01)
		{
			robots = { 3,5 }, distance = { 2,2 }, walls = { 4,6 };
			auto res = Solution().maxWalls(robots, distance, walls);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod11)
		{
			robots = { 4 }, distance = { 3 }, walls = { 1,10 };
			auto res = Solution().maxWalls(robots, distance, walls);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			robots = { 10,2 }, distance = { 5,1 }, walls = { 5,2,7 };
			auto res = Solution().maxWalls(robots, distance, walls);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			robots = { 1,2 }, distance = { 100,1 }, walls = { 10 };
			auto res = Solution().maxWalls(robots, distance, walls);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod14)
		{
			robots = { 17, 59, 32, 11, 72, 18 }, distance = { 5, 7, 6, 5, 2, 10 },
				walls = { 17, 25, 33, 29, 54, 53, 18, 35, 39, 37, 20, 14, 34, 13, 16, 58, 22, 51, 56, 27, 10, 15, 12, 23, 45, 43, 21, 2, 42, 7, 32, 40, 8, 9, 1, 5, 55, 30, 38, 4, 3, 31, 36, 41, 57, 28, 11, 49, 26, 19, 50, 52, 6, 47, 46, 44, 24, 48 };
			auto res = Solution().maxWalls(robots, distance, walls);
			AssertEx(37, res);
		}
		TEST_METHOD(TestMethod15)
		{
			robots = { 31,22,4,43,8,38,5,15,35,37,27,42,40,28,20,21 }, distance = { 3,5,5,7,8,1,10,7,9,6,3,4,4,5,7,4 },
				walls = { 34,74,54,46,79,89,7,73,12,27,44,5,62,43,60,71,10,63,41,77,33,91,32,53,66,51,78,18,61,6,8,24,23,81,3,25,40,85,84,15,52,48,17,59,55,64,50,21,88,36,2,16,80,69,22,87,1,28,65,31,83,26,67,72,29,75,57,9,30,86,39,37,13,19,56,68,35,90 };
			auto res = Solution().maxWalls(robots, distance, walls);
			AssertEx(41, res);
		}
	};

	TEST_CLASS(LC3510)
	{
		//【有序集合 有序映射】 3510. 移除最小数对使数组有序 II|2608
		class Solution {
		public:
			int minimumPairRemoval(vector<int>& nums) {
				int cnt = 0;
				map<int, long long> mNum;
				typedef tuple<long long, int, int> T;
				priority_queue<T,vector<T>,greater<>> minHeap;
				for (int i = 0; i < nums.size();i++) {
					mNum[i] = nums[i];
					if (i)
					{
						minHeap.emplace(mNum[i-1] + mNum[i], i-1, i);
						cnt += nums[i - 1] > nums[i];
					}
				}		

				while (cnt) {
					const auto [sum, i, j] = minHeap.top();minHeap.pop();
					auto iti = mNum.find(i);
					auto itj = mNum.find(j);
					if ((mNum.end() == iti) || (mNum.end() == itj)) {continue;}//i,j都被删除
					if (sum != iti->second + itj->second) { continue; }	
					const auto it1 = (mNum.begin() != iti) ? prev(iti) : mNum.end();
					auto it2 = next(itj);
					cnt -= iti->second > itj->second;
					if (mNum.end() != it1) {
						cnt -= it1->second > iti->second;
					}
					if (mNum.end() != it2) {
						cnt -= itj->second > it2->second;
					}
					iti->second += itj->second;mNum.erase(itj);
					
					if (mNum.begin() != iti) {	
						auto it3 = prev(iti);
						minHeap.emplace(it3->second + iti->second, it3->first, iti->first);
						cnt += it3->second > iti->second;
					}	
					auto it4 = next(iti);
					if (mNum.end() != it4) {
						minHeap.emplace(iti->second+ it4->second,iti->first, it4->first);
						cnt += iti->second > it4->second;
					}
				}
				return nums.size() - mNum.size();
			}
		};
		vector<int> nums;
		TEST_METHOD(TestMethod00)
		{
			nums = { 5,2,3,1 };
			auto res = Solution().minimumPairRemoval(nums);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod01)
		{
			nums = {1,2,2 };
			auto res = Solution().minimumPairRemoval(nums);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod02)
		{
			nums = { 1,1,4,4,2,-4,-1 };
			auto res = Solution().minimumPairRemoval(nums);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod03)
		{
			nums = { -2,1,2,-1,-1,-2,-2,-1,-1,1,1 };
			auto res = Solution().minimumPairRemoval(nums);
			AssertEx(10, res);
		}
	};

	TEST_CLASS(LC3671)
	{
		//【倍数容斥  调和级数 树状数组】LeetCode3671. 子序列美丽值求和|分数未知
		class Solution {
	public:
		int totalBeauty(vector<int>& nums) {			
			typedef C1097Int<> BI;	
			const int M = *max_element(nums.begin(), nums.end());
			vector<BI> cnt1(M+1), cnt2(M+1);
			static auto vDiv = Divis();
			vector<vector<int>> gs(M + 1);
			for (const auto& n : nums) {
				for (const auto& n1 : vDiv[n]) {
					gs[n1].emplace_back(n);
				}
			}
			CTreeArr<BI> bit(M+1);
			for (int i = 1;i <= M;i++) {
				for (const auto& n : gs[i]) {
					bit.Add(n, bit.Sum(n - 1) + 1);
				}
				cnt1[i] = bit.Sum();
				for (const auto& n : gs[i]) {
					auto tmp = bit.Get(n);
					bit.Add(n, tmp*(-1));
				}
			}
			for (int n = M; n > 0;n--) {
				cnt2[n] = cnt1[n];
				for (int i = n * 2; i <= M;i += n) {
					cnt2[n] -= cnt2[i];
				}
			}
			BI ans = 0;
			for (int i = 1;i <= M;i++) {
				ans += cnt2[i] * i;
			}
			return ans.ToInt();
		}
		vector<vector<int>> Divis() {
			const int M = 70000;
			vector<vector<int>> v(1 + M);
			for (int i = 1; i <= M;i++) {
				for (int j = 1;j * j <= i; j++) {
					if (0 != i % j) { continue; }
					v[i].emplace_back(j);
					const int j1 = i / j;
					if (j1 != j) {
						v[i].emplace_back(j1);
					}
				}			
			}
			return v;
		}
		
	};

		vector<int> nums;
		TEST_METHOD(TestMethod00)
		{
			nums = { 1,2,3};
			auto res = Solution().totalBeauty(nums);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod02)
		{
			nums = { 4,6 };
			auto res = Solution().totalBeauty(nums);
			AssertEx(12, res);
		}

	};

	TEST_CLASS(P9349)
	{//P9349 [JOI 2023 Final] Stone Arranging 2

		class Solution {
		public:
			vector<int> Ans(const vector<int>& a) {
				const int N = a.size();
				set<int> inxs;
				unordered_map<int, vector<int>> mColorIndexs;
				for (int i = 0; i < N; i++) {
					int j = i;
					if (mColorIndexs.count(a[i]) && mColorIndexs[a[i]].size()) {
						j = mColorIndexs[a[i]].back();
					};

					for (auto it = inxs.lower_bound(i);;) {
						if (inxs.begin() == it) { break; }
						--it;
						if (*it < j) { break; }
						mColorIndexs[a[*it]].pop_back();
					}
					inxs.erase(inxs.lower_bound(j), inxs.lower_bound(i));
					inxs.emplace(i);
					mColorIndexs[a[i]].emplace_back(i); ;
				}
				vector<int> ans;
				for (int i = 0; i < N; i++) {
					ans.emplace_back(a[*inxs.lower_bound(i)]);
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		TEST_METHOD(TestMethod11)
		{
			a = { 1,2 };
			auto res = Solution().Ans(a);
			AssertV({ 1,2 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = { 1,2 ,1 };
			auto res = Solution().Ans(a);
			AssertV({ 1,1,1 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			a = { 4,1,2,3,2,1 };
			auto res = Solution().Ans(a);
			AssertV({ 4,1,1, 1,1,1 }, res);
		}
		TEST_METHOD(TestMethod14)
		{
			a = { 1,2,1,2,3,2 };
			auto res = Solution().Ans(a);
			AssertV({ 1,1,1,2,2,2 }, res);
		}
		TEST_METHOD(TestMethod15)
		{
			a = { 1,1,2,2,1,2,2,1,1,2 };
			auto res = Solution().Ans(a);
			AssertV({ 1,1,1,1,1,1,1,1,1,2 }, res);
		}
	};	
}

namespace NLeetCode {
	TEST_CLASS(Q1)
	{//P9349 [JOI 2023 Final] Stone Arranging 2
		class Solution {
		public:
			vector<int> sortByReflection(vector<int>& nums) {
				vector<pair<int, int>> tmp;
				for (const auto& n : nums) {
					tmp.emplace_back(make_pair(To(n),n));
				}
				sort(tmp.begin(), tmp.end());
				vector<int> ans;
				for (const auto& [_tmp, n] : tmp) {
					ans.emplace_back(n);
				}
				return ans;
			}
			int To(int n) {
				string str;
				while (n > 0) {
					if (n & 1) {
						str += "1";
					}
					else {
						str += "0";
					}
					n /= 2;
				}
				int i = 0;
				for (; (i < str.length()) && ('0' == str[i]); i++);
				if (str.length() == i) { return 0; }
				int ret = 0;
				for(;i < str.length();i++)
				{
					ret = ret * 2 + ('1' == str[i]);
				}
				return ret;
			}
		}; 
		vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 4,5,4 };
			auto res = Solution().sortByReflection(nums);
			AssertV({ 4,4,5 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 3,6,5,8 };
			auto res = Solution().sortByReflection(nums);
			AssertV({ 8,3,6,5}, res);
		}
	};
	TEST_CLASS(Q2)
	{//P9349 [JOI 2023 Final] Stone Arranging 2
		class Solution {
		public:
			int largestPrime(int n) {
				if (1 == n) { return 0; }
				CCreatePrime cp(n);
				int ret = 0;
				
				int sum = 0;
				for (int j =0; j < cp.m_vPrime.size(); j++) {
					sum += cp.m_vPrime[j];
					if (sum > cp.m_vPrime.back()) { break; }
					if (cp.m_isPrime[sum]) {
						ret = max(ret, sum);
					}
				}
				
				return ret;
			}
		};
	public:
		string s;
			TEST_METHOD(TestMethod11)
			{
				int n = 500'000;
				auto res = Solution().largestPrime(n);
				//AssertEx(4, res);
			}
			TEST_METHOD(TestMethod12)
			{
				int n = 2;
				auto res = Solution().largestPrime(n);
				AssertEx(2, res);
			}
			TEST_METHOD(TestMethod13)
			{
				int n = 20;
				auto res = Solution().largestPrime(n);
				AssertEx(17, res);
			}
	};
	TEST_CLASS(Q3)
	{//【逆序思考 堆】3771. 探索地牢的得分|分数未知
		class Solution {
		public:
			long long totalScore(int hp, vector<int>& damage, vector<int>& requirement) {
				const int N = damage.size();
				priority_queue<long long, vector<long long>, greater<>> minHeap;
				long long td = 0;
				long long ans = 0;
				for (int i = N - 1; i >= 0; i--) {
					minHeap.emplace(td - requirement[i]);
					td += damage[i];
					while (minHeap.size() && (hp - td + minHeap.top() < 0)) { minHeap.pop(); }
					ans += minHeap.size();
				}
				return ans;
			}
		}; 
	public:
		int hp;
		vector<int>damage, requirement;
		TEST_METHOD(TestMethod11)
		{
			hp = 11, damage = { 3,6,7 }, requirement = { 4,2,5 }			;
			auto res = Solution().totalScore(hp, damage, requirement);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			hp = 2, damage = { 10000,1 }, requirement = { 1,1 }			;
			auto res = Solution().totalScore(hp, damage, requirement);
			AssertEx(1LL, res);
		}


	};
	TEST_CLASS(Q4)
	{//【SOSDP模板 容斥原理 逆向思考】3757. 有效子序列的数量|分数未知
		class Solution {
		public:
			vector<int> maxSubgraphScore(int n, vector<vector<int>>& edges, vector<int>& good) {
				this->good = good;
				for (auto& i : this->good) {
					if (0 == i) { i = -1; }
				}
				m_vSub.resize(n);
				m_ans.resize(n);				
				auto neiBo = CNeiBo::Two(n, edges, false);
				DFS(0, -1, neiBo);
				DFS2(0, -1, neiBo);
				return m_ans;
			}
			void DFS(const int cur,const int par,vector<vector<int>>& neiBo) {
				int iChild = 0;
				for (const auto& next : neiBo[cur]) {
					if (par == next) { continue; }
					DFS(next, cur, neiBo);
					if (m_vSub[next] > 0)
					{
						iChild += m_vSub[next];
					}
				}
				m_vSub[cur] = good[cur] + iChild;
			}
			void DFS2(const int cur, const int par, vector<vector<int>>& neiBo) {
				if (-1 == par) {
					m_ans[cur] = m_vSub[cur];
				}
				else {
					const int parS = (m_vSub[cur] > 0) ? (m_ans[par] - m_vSub[cur]) : m_ans[par];
					m_ans[cur] = m_vSub[cur];
					if (parS > 0) { m_ans[cur] += parS; }
				}
				for (const auto& next : neiBo[cur]) {
					if (par == next) { continue; }
					DFS2(next, cur, neiBo);					
				}				
			}
			vector<int> m_vSub, good,m_ans;
		}; 
	public:
		int n;
		vector<vector<int>> edges;
		vector<int> good;
		TEST_METHOD(TestMethod001)
		{
			n = 5, edges = { {1,0},{1,2},{1,3},{3,4} }, good = { 0,1,0,1,1 };			
			auto res = Solution().maxSubgraphScore(n, edges, good);
			AssertEx({ 2,3,2,3,3 }, res);
		}
		TEST_METHOD(TestMethod002)
		{
			n = 2, edges = { {0,1} }, good = { 0,0 };;
			auto res = Solution().maxSubgraphScore(n, edges, good);
			AssertEx({ -1,-1 }, res);
		}
		TEST_METHOD(TestMethod003)
		{
			n = 3, edges = { {0,1},{1,2} }, good = { 1,0,1 }			;
			auto res = Solution().maxSubgraphScore(n, edges, good);
			AssertEx({ 1,1,1 }, res);
		}
		TEST_METHOD(TestMethod004)
		{
			n = 3, edges = { {1,0},{0,2} }, good = { 1,1,1 };
			auto res = Solution().maxSubgraphScore(n, edges, good);
			AssertEx({ 3,3,3 }, res);
		}
	};
}

